home *** CD-ROM | disk | FTP | other *** search
/ Skunkware 5 / Skunkware 5.iso / src / X11 / xconq / mkmap.c < prev    next >
C/C++ Source or Header  |  1995-05-09  |  14KB  |  460 lines
  1. /* Copyright (c) 1987, 1988  Stanley T. Shebs, University of Utah. */
  2. /* This program may be used, copied, modified, and redistributed freely */
  3. /* for noncommercial purposes, so long as this notice remains intact. */
  4.  
  5. #pragma comment(exestr, "@(#) mkmap.c 12.1 95/05/09 ")
  6.  
  7. /* RCS $Header: mkmap.c,v 1.1 88/06/21 12:30:21 shebs Exp $ */
  8.  
  9. /* Terrain generation is based on fractal ideas, although this version */
  10. /* is not directly derived from a published technique. */
  11. /* Speed is important; most of the code has been integerized. */
  12. /* Extra steps produce maps more suitable for conquest, including a way to */
  13. /* control the amount of each type of terrain appearing in the result. */
  14. /* The process is actually done for elevation and water separately, then */
  15. /* the terrain type is dependent on both. */
  16.  
  17. /* (Note that this is no longer a separate program as in the first version.) */
  18.  
  19. #include "config.h"
  20. #include "misc.h"
  21. #include "period.h"
  22. #include "dir.h"
  23. #include "map.h"
  24.  
  25. /* Values of altitude and moisture must be firmly bounded, so that */
  26. /* histogramming doesn't take too much space. */
  27.  
  28. #define MAXALT 16384
  29.  
  30. /* Abstraction of 2D malloced array references.  Names from Lisp... */
  31.  
  32. #define aref(m,x,y) ((m)[(x)+world.width*(y)])
  33.  
  34. #define aset(m,x,y,v) ((m)[(x)+world.width*(y)] = (v))
  35.  
  36. #define aadd(m,x,y,v) ((m)[(x)+world.width*(y)] += (v))
  37.  
  38. /* Values ultimately arriving from the command line. */
  39.  
  40. extern int givenwidth, givenheight, givenseen;
  41.  
  42. /* Arrays here should contain only nonnegative values (for simplicity). */
  43. /* They are potentially large and used only once, so we malloc and free... */
  44.  
  45. int *relief;            /* pointer to array of elevations */
  46. int *water;             /* pointer to array of moisture levels */
  47. int *aux;               /* auxiliary array */
  48. int *histo;             /* histogram array */
  49. int *alts;              /* percentile for each elevation */
  50. int *wets;              /* percentile for level of moisture */
  51.  
  52. /* The main function looks a little strange in spots, since it is derived */
  53. /* from a former standalone program (the mkmap of version 1). */
  54.  
  55. make_up_map()
  56. {
  57.     int width, height;
  58.  
  59.     width = givenwidth;  height = givenheight;
  60.     if (Debug) printf("Going to make up a %dx%d map ...\n", width, height);
  61.     /* Heuristic limit - algorithms get weird on small maps */
  62.     if (width < 9 || height < 9) {
  63.     fprintf(stderr, "Cannot generate such a small map!\n");
  64.     exit(1);
  65.     }
  66.     world.width = width;  world.height = height;
  67.     world.scale = period.scale;
  68.     world.known = givenseen;
  69.     relief = (int *) malloc(world.width * world.height * sizeof(int));
  70.     aux    = (int *) malloc(world.width * world.height * sizeof(int));
  71.     water  = (int *) malloc(world.width * world.height * sizeof(int));
  72.     histo  = (int *) malloc(MAXALT * sizeof(int));
  73.     alts   = (int *) malloc(MAXALT * sizeof(int));
  74.     wets   = (int *) malloc(MAXALT * sizeof(int));
  75.     /* Build a full relief map */
  76.     make_bumps(relief, period.altroughness);
  77.     smooth_map(relief);
  78.     add_curves(relief, period.altroughness);
  79.     smooth_map(relief);
  80.     limit_map(relief, MAXALT-1, 0);
  81.     percentile(relief, alts);
  82.     /* Build a "moisture relief" map */
  83.     make_bumps(water, period.wetroughness);
  84.     smooth_map(water);
  85.     smooth_map(water);
  86.     limit_map(water, MAXALT-1, 0);
  87.     percentile(water, wets);
  88.     /* Put it all together */
  89.     compose_map();
  90.     free(relief);
  91.     free(water);
  92.     free(aux);
  93.     free(histo);
  94.     free(alts);
  95.     free(wets);
  96.     if (Debug) printf("... Done making up a map.\n");
  97. }
  98.  
  99. /* The main map generators produces bumps, of sizes and numbers dictated */
  100. /* by the roughness.  The size is a percentage of map dimensions, while */
  101. /* number is set to approximately cover the entire map.  Each bump is a */
  102. /* hexagonal shape, and the elevation of interior points varies. */
  103.  
  104. make_bumps(map, roughness)
  105. int *map, roughness;
  106. {
  107.     int blocks, i, scale, var, dx, dy, tries;
  108.     int x0, y0, x1, y1, d0, d1, xt, yt, flag, x, y, dz, z, oz;
  109.     int dn1, dn2, dn3, dn4, dn5, dn6, numer1, denom1, numer2, denom2;
  110.     int farx[10], fary[10];
  111.     int peakx[10], peaky[10], peakz[10], peakf[10], numpeaks = 0, p;
  112.  
  113.     scale = max(1, ((100 - roughness) * min(world.width, world.height)) / 100);
  114.     var = MAXALT/8 + (MAXALT/8 * roughness) / 100;
  115.     blocks = (world.width * world.height) / (scale * scale);
  116.     blocks *= 2;
  117.     if (Debug) printf("Playing with blocks (%d)...\n", blocks);
  118.     for (x = 0; x < world.width; ++x) {
  119.     for (y = 0; y < world.height; ++y) {
  120.         aset(map, x, y, MAXALT/2);
  121.     }
  122.     }
  123.     for (i = 0; i < blocks; ++i) {
  124.     flag = ((i == 0 || flip_coin()) ? 1 : -1);
  125.     if (scale <= 1) {
  126.         x = random(world.width) + world.width;
  127.         y = random(world.height);
  128.         z = var + random(var/2);
  129.         aadd(map, wrap(x), y, flag * z);
  130.     } else {
  131.         dx = scale/2 + random(scale/2);
  132.         dy = scale/2 + random(scale/2);
  133.         /* All x values shifted, so as to avoid negatives */
  134.         x0 = random(world.width) + world.width;
  135.         y0 = random(world.height - dy - 1);
  136.         x1 = x0 + dx + 1;
  137.         y1 = y0 + dy + 1;
  138.         d0 = min(x1 - x0, y1 - y0) / 4;
  139.         d0 = d0 + random(3*d0);
  140.         d1 = min(x1 - x0, y1 - y0) / 4;
  141.         d1 = d1 + random(3*d1);
  142.         /* Cheap way to ensure most high points actually within hexagon */
  143.         xt = yt = -1;  tries = 10;
  144.         while (((xt-x0+yt-y0 < d0) || (x1-xt+y1-yt > d1)) && tries-- > 0) {
  145.         xt = x0 + (random(x1 - x0) + random(x1 - x0)) / 2;
  146.         yt = y0 + (random(y1 - y0) + random(y1 - y0)) / 2;
  147.         }
  148.         /* Compute distances from high point to hexagon corners */
  149.         dn1 = distance(xt, yt, x1-d1, y1);
  150.         dn2 = distance(xt, yt, x1, y1-d1);
  151.         dn3 = distance(xt, yt, x1, y0);
  152.         dn4 = distance(xt, yt, x0+d0, y0);
  153.         dn5 = distance(xt, yt, x0, y0+d0);
  154.         dn6 = distance(xt, yt, x0, y1);
  155.         for (y = y0; y <= y1; ++y) {
  156.         for (x = x0; x <= x1; ++x) {
  157.             if ((x-x0+y-y0 > d0) && (x1-x+y1-y > d1)) {
  158.             dx = x - xt;  dy = y - yt;
  159.             if (dx > 0) {
  160.                 if (dy > 0) {
  161.                 numer1 = distance(x, y, x1, y1-d1);
  162.                 denom1 = dn2;
  163.                 numer2 = distance(x, y, x1-d1, y1);
  164.                 denom2 = dn1;
  165.                 } else if (dy > (0 - dx)) {
  166.                 numer1 = distance(x, y, x1, y0);
  167.                 denom1 = dn3;
  168.                 numer2 = distance(x, y, x1, y1-d1);
  169.                 denom2 = dn2;
  170.                 } else {
  171.                 numer1 = distance(x, y, x0+d0, y0);
  172.                 denom1 = dn4;
  173.                 numer2 = distance(x, y, x1, y0);
  174.                 denom2 = dn3;
  175.                 }
  176.             } else {
  177.                 if (dy < 0) {
  178.                 numer1 = distance(x, y, x0, y0+d0);
  179.                 denom1 = dn5;
  180.                 numer2 = distance(x, y, x0+d0, y0);
  181.                 denom2 = dn4;
  182.                 } else if (dy < (0 - dx)) {
  183.                 numer1 = distance(x, y, x0, y1);
  184.                 denom1 = dn6;
  185.                 numer2 = distance(x, y, x0, y0+d0);
  186.                 denom2 = dn5;
  187.                 } else {
  188.                 numer1 = distance(x, y, x1-d1, y1);
  189.                 denom1 = dn1;
  190.                 numer2 = distance(x, y, x0, y1);
  191.                 denom2 = dn6;
  192.                 }
  193.             }
  194.             if (denom1 == 0) denom1 = 1;
  195.             if (denom2 == 0) denom2 = 1;
  196.             dz = (flag * ((var * numer1) / denom1 +
  197.                       (var * numer2) / denom2));
  198.             oz = aref(map, wrap(x), y);
  199.             if (!between(0, dz + oz, MAXALT)) dz /= 2;
  200.             aset(map, wrap(x), y, oz + dz + random(var/2));
  201.             }
  202.         }
  203.         }
  204.     }
  205.     /* Remember some high points for use in hitting untouched areas */
  206.     if (numpeaks < 10) {
  207.         peakx[numpeaks] = wrap(xt);
  208.         peaky[numpeaks] = yt;
  209.         peakf[numpeaks] = flag;
  210.         peakz[numpeaks] = var;
  211.         farx[numpeaks] = wrap(xt+world.width/2);
  212.         fary[numpeaks] = random(world.height);
  213.         numpeaks++;
  214.     }
  215.     }
  216.     /* This is to make smoothly varying terrain in formerly flat areas */
  217.     for (x = 0; x < world.width; ++x) {
  218.     for (y = 0; y < world.height; ++y) {
  219.         if (aref(map, x, y) == MAXALT/2) {
  220.         z = 0;
  221.         for (p = 0; p < numpeaks; ++p) { 
  222.             dz = ((peakz[p] * cyldist(x, y, farx[p], fary[p])) /
  223.               (cyldist(peakx[p], peaky[p], farx[p], fary[p])+1));
  224.             dz -= (peakz[p] * scale) / world.width;
  225.             z += peakf[p] * dz;
  226.         }
  227.         z /= numpeaks;
  228.         aadd(map, x, y, z + random(var/4));
  229.         }
  230.     }
  231.     }
  232.     limit_map(map, MAXALT-1, 0); 
  233. }
  234.  
  235. /* Returns shortest distance around the world (can be either direction). */
  236.  
  237. cyldist(x1, y1, x2, y2)
  238. int x1, y1, x2, y2;
  239. {
  240.     int dist = distance(x1, y1, x2, y2), dist2;
  241.  
  242.     if ((dist2 = distance(x1+world.width, y1, x2, y2)) < dist) {
  243.     dist = dist2;
  244.     } else if ((dist2 = distance(x1, y1, x2+world.width, y2)) < dist) {
  245.     dist = dist2;
  246.     }
  247.     return dist;
  248. }
  249.  
  250. /* Exponent with *small* integer power. (used with Bezier curves) */
  251.  
  252. float
  253. expt(f, i)
  254. float f;
  255. int i;
  256. {
  257.     float rslt = 1.0;
  258.  
  259.     while (i-- > 0) rslt = rslt * f;
  260.     return rslt;
  261. }
  262.  
  263. /* Combination of n objects taken i at a time. (used for Bezier) */
  264.  
  265. comb(n, i)
  266. int n, i;
  267. {
  268.     if (i <= 0) return 1;
  269.     else if (n <= 0) return 0;
  270.     else return (comb(n-1, i) + comb(n-1,i-1));
  271. }
  272.  
  273. /* Put in random Bezier mountain chains.  Number and size are scaled to */
  274. /* the size of the map.  To prevent criss-crossing from creating very */
  275. /* high spots, just set the aux map to values, and only add in later. */
  276.  
  277. add_curves(map, roughness)
  278. int *map, roughness;
  279. {
  280.     int i, j, n, x, y, flag, curves, mindim, var;
  281.     float u, f, cpx[4], cpy[4], px[500], py[500];
  282.  
  283.     curves = (world.width * world.height * roughness) / 50000;
  284.     if (Debug) printf("Throwing curves (%d)...\n", curves);
  285.     for (x = 0; x < world.width; ++x) {
  286.     for (y = 0; y < world.height; ++y) {
  287.         aset(aux, x, y, 0);
  288.     }
  289.     }
  290.     mindim = min(500, min(world.width, world.height));
  291.     var = (MAXALT/8 * roughness) / 100;
  292.     for (n = 0; n < curves; ++n) {
  293.     cpx[0] = 1.0 * (random(world.width-2)+1);
  294.     cpy[0] = 1.0 * (random(world.height-2)+1);
  295.     for (j = 1; j < 4; ++j) {
  296.         cpx[j] = cpx[0] + (random(mindim) - mindim/2);
  297.         if (cpx[j] > world.width-1) cpx[j] = world.width-1;
  298.         if (cpx[j] < 0) cpx[j] = 0;
  299.         cpy[j] = cpy[0] + (random(mindim) - mindim/2);
  300.         if (cpy[j] > world.height-1) cpy[j] = world.height-1;
  301.         if (cpy[j] < 0) cpy[j] = 0;
  302.     }
  303.     for (i = 0; i < mindim; ++i) {
  304.         u = (1.0 * i) / mindim;
  305.         px[i] = py[i] = 0.0;
  306.         for (j = 0; j < 4; ++j) {
  307.         f = comb(3,j)*expt(u,j)*expt(1-u,3-j);
  308.         px[i] += cpx[j]*f; 
  309.         py[i] += cpy[j]*f;
  310.         }
  311.     }
  312.     flag = random(3) ? 1 : -1;
  313.     for (i = 0; i < mindim; ++i) {
  314.         x = (int) px[i];  y = (int) py[i];
  315.         aset(aux, x, y, flag * (MAXALT/8 + var));
  316.     }
  317.     }
  318.     add_maps(map, aux, map);
  319.     limit_map(map, MAXALT-1, 0);
  320. }
  321.  
  322. /* Ensure that map values stay within given range. */
  323.  
  324. limit_map(map, hi, lo)
  325. int *map, hi, lo;
  326. {
  327.     int x, y, m;
  328.     
  329.     for (x = 0; x < world.width; ++x) {
  330.     for (y = 0; y < world.height; ++y) {
  331.         m = aref(map, x, y);
  332.         aset(map, x, y, max(lo, min(m, hi)));
  333.     }
  334.     }
  335. }
  336.  
  337. /* Form the point-wise sum of two maps into a third one. */
  338.  
  339. add_maps(m1, m2, rslt)
  340. int *m1, *m2, *rslt;
  341. {
  342.     int x, y;
  343.  
  344.     for (x = 0; x < world.width; ++x) {
  345.     for (y = 0; y < world.height; ++y) {
  346.         aset(rslt, x, y, aref(m1, x, y) + aref(m2, x, y));
  347.     }
  348.     }
  349. }
  350.  
  351. /* Average out things to keep peaks from getting too sharp. */
  352. /* The array "aux" is the buffer for this operation. */
  353. /* The edges of the map remain unaltered. (dubious) */
  354.  
  355. smooth_map(map)
  356. int *map;
  357. {
  358.     int x, y, nx, px, sum;
  359.  
  360.     if (Debug) printf("Smoothing...\n");
  361.     for (x = 0; x < world.width; ++x) {
  362.     nx = wrap(x+1);  px = wrap(x-1);
  363.     for (y = 1; y < world.height-1; ++y) {
  364.         sum  = aref(map, x, y);
  365.         sum += aref(map, x, y+1);
  366.         sum += aref(map, nx, y);
  367.         sum += aref(map, nx, y-1);
  368.         sum += aref(map, x, y-1);
  369.         sum += aref(map, px, y);
  370.         sum += aref(map, px, y+1);
  371.         aset(aux, x, y, sum / 7);
  372.     }
  373.     }
  374.     for (x = 0; x < world.width; ++x) {
  375.     for (y = 1; y < world.height-1; ++y) {
  376.         aset(map, x, y, aref(aux, x, y));
  377.     }
  378.     }
  379. }
  380.  
  381. /* Terrain types are specified in terms of percentage cover on a map, so */
  382. /* for instance the Earth is 70% sea.  Since each of several types will have */
  383. /* its own percentages (both for elevation and moisture), the simplest thing */
  384. /* to do is to calculate the percentile for each elevation and moisture */
  385. /* level, and save them all away.  This would be a one-liner in APL... */
  386.  
  387. /* Percentile computation is inefficient, should be done incrementally */
  388. /* somehow instead of with * and / */
  389.  
  390. percentile(map, percentiles)
  391. int *map, *percentiles;
  392. {
  393.     int i, x, y, total;
  394.     
  395.     if (Debug) printf("Computing percentiles...\n");
  396.     for (i = 0; i < MAXALT; ++i) {
  397.     histo[i] = 0;
  398.     percentiles[i] = 0;
  399.     }
  400.     /* Make the basic histogram, but don't count the edges */
  401.     for (x = 0; x < world.width; ++x) {
  402.     for (y = 1; y < world.height-1; ++y) {
  403.         ++histo[aref(map, x, y)];
  404.     }
  405.     }
  406.     /* Integrate over the histogram */
  407.     for (i = 1; i < MAXALT; ++i)
  408.     histo[i] += histo[i-1];
  409.     /* Total here should actually be the same as number of cells in the map */
  410.     total = histo[MAXALT-1];
  411.     /* Compute the percentile position */
  412.     for (i = 0; i < MAXALT; ++i)
  413.     percentiles[i] = (100 * histo[i]) / total;
  414. }
  415.  
  416. /* Final creation and output of the map. */
  417.  
  418. compose_map()
  419. {
  420.     int x, y;
  421.  
  422.     if (Debug) printf("Assigning terrain types...\n");
  423.     allocate_map();
  424.     for (y = 0; y < world.height; ++y) {
  425.     for (x = 0; x < world.width; ++x) {
  426.         set_terrain_at(x, y, terrain(x, y));
  427.         set_unit_at(x, y, NULL);
  428.     }
  429.     }
  430.     /* Add a border if specified */
  431.     if (period.edgeterrain >= 0) {
  432.     for (x = 0; x < world.width; ++x) {
  433.         set_terrain_at(x, 0, period.edgeterrain);
  434.         set_terrain_at(x, world.height-1, period.edgeterrain);
  435.     }
  436.     }
  437. }
  438.  
  439. /* Do final output of terrain types.  This is basically a process of */
  440. /* checking the percentile limits on each type against what is actually */
  441. /* there.  (could and maybe should be more efficient) */
  442. /* Error checking important for period designers... */
  443.  
  444. terrain(x, y)
  445. int x, y;
  446. {
  447.     int t, a = aref(relief, x, y), w = aref(water, x, y);
  448.  
  449.     for_all_terrain_types(t) {
  450.     if (between(ttypes[t].minalt, alts[a], ttypes[t].maxalt) &&
  451.         between(ttypes[t].minwet, wets[w], ttypes[t].maxwet)) {
  452.         return t;
  453.     }
  454.     }
  455.     printf("Unknown terrain in percentiles alt %d, wet %d.\n",
  456.        alts[a], wets[w]);
  457.     /* Not great, but valid if nothing else */
  458.     return (max(0, period.defaultterrain));
  459. }
  460.